package J3_5;

public class test {
    //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    //
    //请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int i = 0;
        while (i<len) {
            if (nums[i] == 0) {
                for (int j = i; j < len-1; j++) {
                    nums[j] = nums[j+1];
                }
                nums[len-1] = 0;
                len--;
            }else {
                i++;
            }
        }

    }

    //给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
    //
    //「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
   }

    public int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return goodNode(root,root.val);
    }

    public int goodNode(TreeNode root,int cur) {
        if (root == null) {
            return 0;
        }
        if (root.val >= cur) {
            return goodNode(root.left, root.val)+goodNode(root.right,root.val)+1;
        }else {
            return goodNode(root.left,cur)+goodNode(root.right,cur);
        }
    }

    //实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
    /*public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left)-height(root.right))<=1 && isBalanced(root.right) && isBalanced(root.left);
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left),height(root.right))+1;
    }*/
    public boolean isBalanced(TreeNode root) {
        return !(height(root) == -1);
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (height(root.left) == -1 || height(root.right) == -1 || Math.abs(height(root.right)-height(root.left))<=1) {
            return -1;
        }
        return Math.max(height(root.left),height(root.right))+1;
    }


}
